/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：Graph.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-17
Function List ：
Description   ：Adjacency List
******************************************************/

#include "Graph.h"
#include <stdlib.h>   // for malloc
#include "FatalError.h"

#define MaxVertexNum     (16)

struct ArcNode {
    int      AdjVex;
    ArcType  Weight;
    Position Next;
};

struct VertexNode {
    VertexType Data;
    Position   First;
};

struct GraphNode {
    AdjList *Vertices;
    int NumVertex;
    int NumArc;
};

// Static Function Lists
static void DeleteArcList(ArcList L);
static int LocateVertex(VertexType V, Graph G);

Graph Initialize(void) {
    Graph G;
    int i;

    /* Allocate graph */
    G = (Graph)malloc(sizeof(struct GraphNode));
    if (G == NULL) {
        FatalError("Out of space!!!");
    }

    /* Allocate the array for vertices */
    G->Vertices = (AdjList *)malloc(MaxVertexNum * sizeof(AdjList));
    if (G->Vertices == NULL) {
        FatalError("Out of space!!!");
    }

    for (i = 0; i < MaxVertexNum; ++i) {
        G->Vertices[i].First = NULL;
    }

    return G;
}

void MakeEmpty(Graph G) {
    int i;

    for (i = 0; i < MaxVertexNum; ++i) {
        if (G->Vertices[i].First != NULL) {
            DeleteArcList(G->Vertices[i].First);
        }
    }

    G->NumVertex = 0;
    G->NumArc = 0;
}

void Destroy(Graph G) {
    MakeEmpty(G);
    free(G->Vertices);
    free(G);
}

int IsEmpty(Graph G) {
    return G->NumVertex == 0;
}

int IsFull(Graph G) {
    return G->NumVertex == MaxVertexNum;
}

static void DeleteArcList(ArcList L) {
    Position P, TmpCell;

    P = L;
    L->Next = NULL;
    while (P != NULL) {
        TmpCell = P->Next;
        free(P);
        P = TmpCell;
    }
}

/* If Vertex is found, then index of returned */
/* the location */
static int LocateVertex(VertexType V, Graph G) {
    int i;

    for (i = 0; i < G->NumVertex; ++i) {
        /* Probably need strcmp! */
        if (V == G->Vertices[i].Data) {
            return i;
        }
    }

    return -1;
}

void InsertVertex(VertexType V, Graph G) {
    if (!IsFull(G)) {
        // Check vertex in graph
        if (LocateVertex(V, G) != -1) {
            Error("Vertex V already exists!");
        } else {
            G->Vertices[G->NumVertex].Data = V;
            ++G->NumVertex;
        }
    }
}

void InsertArc(VertexType VS, VertexType VE, ArcType Weight, Graph G) {
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    // Check vertex in graph
    if (StartIndex == -1) {
        Error("Vertex VS is not found!");
    } else if (EndIndex == -1) {
        Error("Vertex VE is not found!");
    } else {
        if (StartIndex != EndIndex) {
            Position TmpCell = (Position)malloc(sizeof(struct ArcNode));
            if (TmpCell == NULL) {
                FatalError("Out of space!!!");
            }

            /* Insert header */
            TmpCell->AdjVex = EndIndex;
            TmpCell->Weight = Weight;
            TmpCell->Next = G->Vertices[StartIndex].First;
            G->Vertices[StartIndex].First = TmpCell;
            ++G->NumArc;

#ifdef UndirectedGraph
            TmpCell = (Position)malloc(sizeof(struct ArcNode));
            if (TmpCell == NULL) {
                FatalError("Out of space!!!");
            }

            /* Insert header */
            TmpCell->AdjVex = StartIndex;
            TmpCell->Weight = Weight;
            TmpCell->Next = G->Vertices[EndIndex].First;
            G->Vertices[EndIndex].First = TmpCell;
            ++G->NumArc;
#endif
        } else {
            Error("Vertex VS is same as Vertex VE!");
        }
    }
}

void RemoveVertex(VertexType V, Graph G) {
    int Index;
    int i;

    if (!IsEmpty(G)) {
        Index = LocateVertex(V, G);

        // Check vertex in graph
        if (Index != -1) {
            if (Index != G->NumVertex) {
                // Delete vertex
                G->Vertices[Index] = G->Vertices[G->NumVertex - 1];
            }

            // Update the number of vertices
            --G->NumVertex;

            // Delete the arcs of vertices
            for (i = 0; i < G->NumVertex; ++i) {
                Position Cur = G->Vertices[Index].First;
                Position Pre = Cur;
                while (Cur != NULL) {
                    if (G->Vertices[Cur->AdjVex].Data == V) {
                        Pre->Next = Cur->Next;
                        free(Cur);
                        break;
                    } else {
                        Pre = Cur;
                        Cur = Cur->Next;
                    }
                }
            }
        }
    }
}

void RemoveArc(VertexType VS, VertexType VE, Graph G) {
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    // Check vertex in graph
    if (StartIndex == -1) {
        Error("Vertex VS is not found!");
    } else if (EndIndex == -1) {
        Error("Vertex VE is not found!");
    } else {
        if (VS != VE) {
            Position Cur = G->Vertices[StartIndex].First;
            Position Pre = Cur;
            while (Cur != NULL) {
                if (Cur->AdjVex == EndIndex) {
                    Pre->Next = Cur->Next;
                    free(Cur);
                    break;
                } else {
                    Pre = Cur;
                    Cur = Cur->Next;
                }
            }

            --G->NumArc;

#ifdef UndirectedGraph
            Cur = G->Vertices[EndIndex].First;
            Pre = Cur;
            while (Cur != NULL) {
                if (Cur->AdjVex == StartIndex) {
                    Pre->Next = Cur->Next;
                    free(Cur);
                    break;
                } else {
                    Pre = Cur;
                    Cur = Cur->Next;
                }
            }

            --G->NumArc;
#endif
        } else {
            Error("Vertex VS is same as Vertex VE!");
        }
    }
}

int N(Graph G) {
    return G->NumVertex;
}

int E(Graph G) {
    return G->NumArc;
}

ArcType Weight(VertexType VS, VertexType VE, Graph G) {
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    if (StartIndex != -1) {
        Position P = G->Vertices[StartIndex].First;
        while (P != NULL) {
            if (P->AdjVex == EndIndex) {
                break;
            } else {
                P = P->Next;
            }
        }

        if (P != NULL) {
            return P->Weight;
        } else {
            return Infinity;
        }
    } else {
        return Infinity;
    }
}

VertexType Vertex(int Index, Graph G) {
    return G->Vertices[Index].Data;
}

ArcList First(int Index, Graph G) {
    return G->Vertices[Index].First;
}

ArcList Next(ArcList L, Graph G) {
    return L->Next;
}

int Index(ArcList L, Graph G) {
    return L->AdjVex;
}

ArcType ArcWeight(ArcList L, Graph G) {
    return L->Weight;
}

// EOF

